// This is quick sort algorithm implementation.
#include<stdio.h>

void swap(int * a, int * b) 
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

size_t partition(int * arr, int l, int r) 
{
	int i = l + 1, j = r;
	int pivot = arr[l];	
	while (i <= j) 
	{
		while (pivot < arr[j])
			j--;
		if (j == l)
			return l;
		while (i < r && pivot > arr[i])
			i++;
		if (i == j) break;
		if (i < j)
			swap(&arr[i], &arr[j]);
	}
	swap(&arr[l], &arr[j]);	
	return j;
}

void qsort(int * arr, int l , int r) 
{

	if (l >= r)
		return;
	int pivot_pos = partition(arr, l, r);
	qsort(arr, l, pivot_pos - 1);
	qsort(arr, pivot_pos + 1, r);		
}

void display(int * arr, int n) 
{
	for (int i = 0; i < n; i++)
		printf(" \n%d ", arr[i]);
}


int main() 
{
	int n = 8;
	int arr[] = { 3, 1, 2, 5, 6, 3, 8, 7 };
	// int arr[] = { 1, 2, 3, 7 };
	// int arr[] = { 8, 6, 7};
	qsort(arr, 0, n - 1);
	display(arr, n);
}